package org.basic.algorithm.medium;

import org.basic.common.annotations.Result;

/**
 * Z字形变换
 * <p>
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 * <p>
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * <p>
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 * <p>
 * 示例 1：
 * 输入：s = "PAYPALISHIRING", numRows = 3
 * 输出："PAHNAPLSIIGYIR"
 * <p>
 * 示例 2：
 * 输入：s = "PAYPALISHIRING", numRows = 4
 * 输出："PINALSIGYAHRPI"
 * 解释：
 * P     I    N
 * A   L S  I G
 * Y A   H R
 * P     I
 * <p>
 * 示例 3：
 * 输入：s = "A", numRows = 1
 * 输出："A"
 * <p>
 * 提示：
 * 1 <= s.length <= 1000
 * s 由英文字母（小写和大写）、',' 和 '.' 组成
 * 1 <= numRows <= 1000
 *
 * @author LiKun
 * @date 2021/10/15 10:38
 */
public class ZigzagConversion {
    public static void main(String[] args) {
        System.out.println(convert("AB", 1));
    }

    @Result(time = {4, 6}, memory = {38.6, 38.9})
    public static String convert(String s, int numRows) {
        if (s.length() <= numRows || numRows < 2) {
            return s;
        } else {
            char[] chars = s.toCharArray();
            int y = 0, x = 0, index = 0, innerIndex;
            StringBuilder builder = new StringBuilder();
            int quantity = numRows - 1 << 1, circle = chars.length / quantity + 1;
            char[][] cache = new char[numRows][circle << 1];

            for (int i = 0; i < circle; i++) {
                innerIndex = 1;
                while (index < chars.length) {
                    if (innerIndex > quantity) {                                     // 遍历到最后一个节点
                        x++;
                        break;
                    } else if (innerIndex < numRows) {                               // 遍历最低节点前的节点
                        cache[y++][x] = chars[index++];
                    } else if (innerIndex == numRows) {                              // 遍历到最低节点
                        cache[y--][x++] = chars[index++];
                    } else {                                                         // 遍历最低节点后的节点
                        cache[y--][x] = chars[index++];
                    }

                    innerIndex++;
                }
            }

            for (char[] charArr : cache) {
                for (char c : charArr) {
                    if (c != '\u0000') {
                        builder.append(c);
                    }
                }
            }

            return builder.toString();
        }
    }
}
